
let arr1 = [3,4,1,2,0,5,6]
//快排
function quickSort(arr){
    if(arr.length === 0){
        return []
    }
    let lesser = [] //存储更小的值
    let greater = [] //存储更大的值
    let pivot = arr[0] //在数组中取一个基准值，用于把更大和更小的值对比出来，默认取数组第一项

    //接下来做一个循环，从1位开始，因为0位已经被用于基准值
    for(let i = 1; i < arr.length; i++){
        if(arr[i] < pivot){ //如果小于基准值，放到更小的数组中
            lesser.push(arr[i])
        }else{ //否则放到更大的数组中去
            greater.push(arr[i])
        }
    }
    //开始递归，继续拆分数组
    return quickSort(lesser).concat(pivot,quickSort(greater))
}

quickSort(arr1) //注意返回的是新数组，不修改原数组


//创建随机数组的函数
function createArray(length){
    let array = new Array(length);
    for(let i = 0, len = length; i< len;i++){
        array[i] = Math.floor(Math.random()*length)
    }
    return array;
}
let array =createArray(100000);

//万老改进的快排
//思路：不停地进行以下操作 取中间值，把小的放左边，大的放右边，直至完成排序
function quickSort2(arr){
    return quick(arr,0,arr.length-1)
}

function quick(arr,left,right){ //取一个中间值，把小于中间值的放左边，大于中间值的放右边
    let index
    if(arr.length > 1){
        index = partition(arr,left,right) //取中间索引
        if(left < index - 1){ //左侧
            quick(arr,left,index - 1)
        }
        if(index < right){ //右侧
            quick(arr,index,right)
        }
    }
    return arr
}

function partition(arr,left,right){ //用于取中间值的函数
    let pivot = arr[Math.floor((right + left)/2)] //取此次遍历时的中间值
    let i = left //左边
    let j = right //右边
    while(i < j){
        while(arr[i] < pivot){
            i++
        }
        while(arr[j] > pivot){
            j--
        }
        if(i <= j){
            swap(arr,i,j) //交换数组左右边的值
            i++
            j--
        }
    }
    return i //返回中间值i（其实返回i或者j都一样）
}

function swap(arr,i,j){ //用于交换的函数
    let temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp
}
console.log(array)
console.time(`快排2的时间`)
quickSort2(array)
console.timeEnd(`快排2的时间`)
console.log(array)

//快排3 代码量小一些
function quickSort3(arr){
    function quickSort(arr,left,right){
        let l = left
        let r = right
        if(l>=r) return //递归出口
        while(l < r){
            while(arr[l] <= arr[r] && l < r){
                l++
            }
            swap(arr,l,r)

            while(arr[l] <= arr[r] && l < r){
                r--
            }
            swap(arr,l,r)
        }
        let middle = r //取中间值
        quickSort(arr,left,middle-1)
        quickSort(arr,middle,right)
    }
    quickSort(arr,0,arr.length-1)
}

function swap(arr,i,j){ //用于交换的函数
    let temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp
}

let arr3 = [3,5,2,1,0,9,8,6,4,7]
console.log(arr3)
quickSort3(arr3)
console.log(arr3)